package leetcode;

import java.util.*;

/**
 * 373.查找和最小的K对数字
 * 给定两个以 升序排列 的整数数组 nums1 和 nums2,以及一个整数 k。
 * 定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2.
 *
 * 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
 * 输出: [1,2],[1,4],[1,6]
 * 解释: 返回序列中的前 3 对数：
 *      [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
 */
public class Num_373 {
    //自定义类，存储数对
    private class Nums {
        int u;
        int v;
        public Nums(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //改造为最大堆
        Queue<Nums> queue = new PriorityQueue<>(new Comparator<Nums>() {
            @Override
            public int compare(Nums o1, Nums o2) {
                return (o2.u+o2.v) - (o1.u+o1.v);
            }
        });
        //开始二重遍历,注意终止条件的判定
        for(int i=0; i<Math.min(nums1.length, k); i++){
            for(int j=0; j<Math.min(nums2.length, k); j++){
                if(queue.size() < k){
                    //直接添加
                    queue.offer(new Nums(nums1[i],nums2[j]));
                }else if(queue.peek().u + queue.peek().v > nums1[i] + nums2[j]){
                    //如果堆顶元素和 > 该组元素和，先让堆顶元素出队
                    queue.poll();
                    //再将该组元素入队
                    queue.offer(new Nums(nums1[i],nums2[j]));
                }
            }
        }
        //此时堆中存放了k个最小数对
        List<List<Integer>> list = new ArrayList<>();
        while(!queue.isEmpty()){
            //建立内部数组存储这一对数字
            List<Integer> inner = new ArrayList<>();
            inner.add(queue.peek().u);
            inner.add(queue.peek().v);
            //添加到list中
            list.add(inner);
            //堆顶出队
            queue.poll();
        }
        return list;
    }
}
